import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;

    public static String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }

        return st.nextToken();
    }

    public static String nextLine() throws IOException {
        return br.readLine();
    }

    public static boolean hasNext() throws IOException {
        return br.ready();
    }

    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static int[]e,w,ne,h,dis;
    static int idx;
    static int[] p;
    static boolean[] is;
    static int n,m;

    public static void main(String[] args) throws IOException{
         n=nextInt();
         m=nextInt();

        dis=new int[n+1];
        h=new int[2*m+1];
        w=new int[2*m+1];
        e=new int[2*m+1];             //堆优化的初始化
        ne=new int[2*m+1];
        is=new boolean[n+1];

        p=new int[n+1];          //并查集的初始化
        edags=new int[m][3];    //这里边要刚好长度m,不然排序会因为多余的边出现错误

        Arrays.fill(h,-1);


        for(int i=0;i<m;i++){
            int a=nextInt();
            int b=nextInt();
            int c=nextInt();

            add(a,b,c);
            add(b,a,c);

            edags[i][0]=a;
            edags[i][1]=b;
            edags[i][2]=c;




        }


        System.out.println(prim(1));       //任何点开始都可以得到最小生成树
        System.out.println(ki());

    }

    static int prim(int x){

        Arrays.fill(dis,0x3f3f3f3f);

        int ret=0;


        PriorityQueue<int[]> q=new PriorityQueue<>((a,b)->{
            return a[0]-b[0];
        });
        q.add(new int[]{0,x});
        dis[x]=0;



        while (!q.isEmpty()){
            int[] arr=q.poll();
            int distance=arr[0];
            int ver=arr[1];
            if(is[ver]) continue;
            is[ver]=true;
//            System.out.println("ver: "+ver+"  distance: "+distance);    //超绝打印找出bug，无向图需要双向add
            ret+=distance;
            for(int i=h[ver];i!=-1;i=ne[i]){
                int j=e[i];
                if(dis[j]>w[i]){
                    dis[j]=w[i];
                    q.add(new int[]{w[i],j});
                }
            }


        }

        return ret;

    }

    static void add(int a,int b,int c){
        e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
    }




    static int[][] edags;

    static int find(int x){
        if(x!=p[x]) p[x]=find(p[x]);

        return p[x];


    }



    static int ki(){
        int ret=0;
        int cnt=0;
        for(int i=0;i<p.length;i++){
            p[i]=i;
        }

        Arrays.sort(edags,(a,b)->a[2]-b[2]);


        for(int i=0;i<m;i++){

            int a=edags[i][0];
            int b=edags[i][1];

            System.out.println(a+" "+b);



            int x=find(a);
            int y=find(b);

            System.out.println(x+" "+y);

            if(x!=y){

                ret+=edags[i][2];
                if(++cnt>=n) return ret;
                p[a]=b;


            }
        }

        return ret;


    }



}
